package example.连续部分.位置随机;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

// NC41 最长无重复子数组
public class Demo2 {
    /**
     * 我们使用两个指针，一个i一个j，最开始的时候i和j指向第一个元素，
     * 然后i往后移，把扫描过的元素都放到map中，如果i扫描过的元素没有重复的就一直往后移，
     * 顺便记录一下最大值max，如果i扫描过的元素有重复的，就改变j的位置
     *
     * @param arr
     * @return
     */
    public int maxLength(int[] arr) {
        if (arr.length == 0)
            return 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        int max = 0;
        for (int i = 0, j = 0; i < arr.length; ++i) {
            if (map.containsKey(arr[i])) {
                j = Math.max(j, map.get(arr[i]) + 1);
            }
            map.put(arr[i], i);
            max = Math.max(max, i - j + 1);
        }
        return max;
    }

    /**
     *
     * 我们还可以用一个队列，把元素不停的加入到队列中，如果有相同的元素，
     * 就把队首的元素移除，这样我们就可以保证队列中永远都没有重复的元素
     *
     * @param arr
     * @return
     */
    public int maxLength2(int[] arr) {
        //用链表实现队列，队列是先进先出的
        Queue<Integer> queue = new LinkedList<>();
        int res = 0;
        for (int c : arr) {
            // 数组元素 1 2 2 2 4 5 6 7 8 9
            while (queue.contains(c)) {
                //如果有重复的，队头出队
                queue.poll();
            }
            //添加到队尾
            queue.add(c);
            res = Math.max(res, queue.size());
        }
        return res;
    }

    public static void main(String[] args) {

    }
}
